package com.demo.java.OD401_450.OD405;

import java.util.Scanner;

/**
 * @author bug菌
 * @Source 公众号：猿圈奇妙屋
 * @des： 【悄悄话花费的时间(C&D卷)】问题
 * @url： https://blog.csdn.net/weixin_43970743/article/details/146252182
 */
public class OdMain {
    static class TreeNode {
        int value;
        TreeNode left, right;

        public TreeNode(int value) {
            this.value = value;
            this.left = this.right = null;
        }
    }

    // 计算节点接收悄悄话的时间
    public static int calculateReceiveTime(TreeNode root) {
        if (root == null) {
            return 0;  // 空节点的接收时间为0
        }

        // 递归计算左右子树的接收时间
        int leftTime = calculateReceiveTime(root.left);
        int rightTime = calculateReceiveTime(root.right);

        // 当前节点的接收时间等于左右子树中较大的接收时间加上当前节点的值
        int currentTime = Math.max(leftTime, rightTime) + root.value;

        return currentTime;
    }

    // 根据数组构建二叉树
    public static TreeNode buildTree(int[] nums, int index) {
        if (index < nums.length && nums[index] != -1) {
            TreeNode root = new TreeNode(nums[index]);
            root.left = buildTree(nums, 2 * index + 1);  // 构建左子树
            root.right = buildTree(nums, 2 * index + 2); // 构建右子树
            return root;
        }
        return null;  // 如果当前节点为-1，返回null表示空节点
    }

    public static void main(String[] args) {
        // 使用Scanner从控制台读取输入
        Scanner scanner = new Scanner(System.in);

        // 提示用户输入树的节点数组
        System.out.println("请输入树的节点（以空格分隔，-1表示空节点）：");
        String input = scanner.nextLine(); // 读取输入的整行字符串

        // 将输入的字符串转换为整数数组
        String[] parts = input.split(" ");
        int[] nums = new int[parts.length];
        for (int i = 0; i < parts.length; i++) {
            nums[i] = Integer.parseInt(parts[i]); // 转换为整数并存储到数组中
        }

        // 构建二叉树
        TreeNode root = buildTree(nums, 0);

        // 计算所有节点接收悄悄话的时间
        int result = calculateReceiveTime(root);

        // 输出结果
        System.out.println("所有节点接收悄悄话的总时间: " + result);
    }
}
